package com.lihepeng.leecode.tree;

import java.util.LinkedList;
import java.util.List;

/**
 *  给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，
 *  使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 */
public class Solution897 {
    List<Integer> lists = new LinkedList<>();
    public TreeNode increasingBST(TreeNode root) {
        // 中序遍历查询
        inOrder(root);
        // 根据列表中的内容重新构建
        TreeNode treeNode = new TreeNode(-1);
        TreeNode curNode = treeNode;
        for(Integer val:lists){
            curNode.right =  new TreeNode(val);
            curNode = curNode.right;
        }
        return treeNode.right;
    }
    private void inOrder(TreeNode node){
        if(node ==null){
            return;
        }
        inOrder(node.left);
        lists.add(node.val);
        inOrder(node.right);
    }

}
